package com.nl.trees;

import java.util.Iterator;
import java.util.Stack;

import com.nl.trees.BTree.Node;

public class BtreePathEquqlExpectValue {

	private static class Path{
		Stack<Node<Integer>> path =null;
		int currentSum = 0;
		public Path(){
			this.path = new Stack<Node<Integer>>();	
			this.currentSum=0;
		}
		
		public void push(Node<Integer>node){
			path.push(node);
			currentSum+=node.value;
		}
		public void pop(){
			currentSum-=path.pop().value;
		}
	}
	

	public static void findPath(BTree.Node<Integer> proot,int expectValue){
		if(proot == null){
			return;
		}
		Path path = new Path();
		findPath(proot,expectValue,path);
	}
	
	private static void findPath(Node<Integer> proot, int expectValue,Path path) {
		//将当前节点加入路径
		path.push(proot);
		boolean isLeaf = proot.left == null && proot.right == null;
		//如果是叶节点并且路径和为给定值,打印路径信息
		if(isLeaf&&path.currentSum== expectValue){
			Iterator<Node<Integer>>iter = path.path.iterator();
			while(iter.hasNext()){
				System.out.print(iter.next().value+" \t");
			}
			System.out.println();
		}
		
		//左子树不为空，继续寻找
		if(proot.left!=null){
			findPath(proot.left, expectValue, path);
		}
		
		//右子树不为空，继续寻找
		if(proot.right != null){
			findPath(proot.right, expectValue, path);
		}
		//返回根结点，删除当前节点并减去当前节点值
		path.pop();
	}

	public static void main(String[] args) {
		BTree<Integer> tree = new BTree<Integer>();
		tree.build(new Integer[]{10,5,4,7,12},new Integer[]{4,5,7,10,12});
		findPath(tree.root,22);
	}
}
